package _18_剑指OfferII;

import java.util.*;

public class _111_剑指OfferII计算除法 {

    public static void main(String[] args) {

        _111_剑指OfferII计算除法 v = new _111_剑指OfferII计算除法();

        ArrayList<List<String>> results1 = new ArrayList<>();
        ArrayList<String> list1 = new ArrayList<>();
        list1.add("a");
        list1.add("b");
        ArrayList<String> list2 = new ArrayList<>();
        list2.add("b");
        list2.add("c");
        results1.add(list1);
        results1.add(list2);
        double[] values = {2.0, 3.0};
        ArrayList<List<String>> results2 = new ArrayList<>();
        ArrayList<String> list3 = new ArrayList<>();
        list3.add("a");
        list3.add("c");
        results2.add(list3);
        ArrayList<String> list4 = new ArrayList<>();
        list4.add("b");
        list4.add("a");
        results2.add(list4);

        System.out.println(Arrays.toString(v.calcEquation(results1, values, results2)));

    }

    // 构建图, 然后广度优先搜索获取值
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        int nav = 0;
        Map<String, Integer> map = new HashMap<>();
        int eqLen = equations.size();
        for (List<String> equation : equations) {
            if (!map.containsKey(equation.get(0))) {
                map.put(equation.get(0), nav++);
            }
            if (!map.containsKey(equation.get(1))) {
                map.put(equation.get(1), nav++);
            }
        }

        // 构建权值集合
        List<Pair>[] weights = new List[nav];
        for (int i = 0; i < nav; ++i) {
            weights[i] = new ArrayList<>();
        }
        // 构造数组存放数据
        for (int i = 0; i < eqLen; ++i) {
            int fistIndex = map.get(equations.get(i).get(0));
            int lastIndex = map.get(equations.get(i).get(1));
            weights[fistIndex].add(new Pair(lastIndex, values[i]));
            weights[lastIndex].add(new Pair(fistIndex, 1 / values[i]));
        }
        int qLen = queries.size();
        double[] results = new double[qLen];
        for (int i = 0; i < qLen; ++i) {
            String source = queries.get(i).get(0);
            String target = queries.get(i).get(1);
            if (!map.containsKey(source) || !map.containsKey(target)) {
                results[i] = -1.0;
                continue;
            }
            int sourceIndex = map.get(source);
            int targetIndex = map.get(target);
            if (sourceIndex == targetIndex) {
                results[i] = 1.0;
            } else {
                // 广度搜索结果
                double[] temp = new double[nav];
                Arrays.fill(temp, -1);
                temp[sourceIndex] = 1;
                LinkedList<Integer> queue = new LinkedList<>();
                queue.offer(sourceIndex);
                while (!queue.isEmpty() && temp[targetIndex] == -1) {
                    int index = queue.poll();
                    for (Pair pair : weights[index]) {
                        if (temp[pair.index] == -1) {
                            temp[pair.index] = temp[index] * pair.value;
                            queue.offer(pair.index);
                        }
                    }
                }
                results[i] = temp[targetIndex];
            }
        }
        return results;
    }


    static class Pair {
        int index;

        double value;

        public Pair(int index, double value) {
            this.index = index;
            this.value = value;
        }
    }

}
